package com.lsa.helpers.tree.binary;

import java.util.Comparator;

import com.lsa.helpers.tree.Tree;

public class BinaryTree<T> extends Tree<T> {
	
	private Comparator<T> comparator;
	private boolean isNonDeterministicRemoval = true;
	private boolean isDeterministicallyRemoveWithLeft = true;

	public BinaryTree(Comparator<T> comparator) {
		super(null);
		this.comparator= comparator;
	}
	
	public void setNonDeterministicRemoval(boolean isNonDeterministicRemoval) {
		this.isNonDeterministicRemoval = isNonDeterministicRemoval;
	}

	public void setDeterministicallyRemoveWithLeft(
			boolean isDeterministicallyRemoveWithLeft) {
		this.isDeterministicallyRemoveWithLeft = isDeterministicallyRemoveWithLeft;
	}

	@Override
    public IBinaryTreeNode<T> getRoot()
    {
        return (IBinaryTreeNode<T>)root;
    }
	
	public IBinaryTreeNode<T> search(T val){
		return searchInner(val).node;
	}
	
	private SearchResult<T> searchInner(T val){
		SearchResult<T>  returnValue = new SearchResult<T>(); 
		IBinaryTreeNode<T> parent = null;
		IBinaryTreeNode<T> root = getRoot();
		boolean isLeft = false;
		while(root != null){
			final IBinaryTreeNode<T> n = root;
			int comparisonResult = comparator.compare(root.getData(), val);
			if (comparisonResult == 0) {
				returnValue.parent = parent;
				returnValue.node = root;
				returnValue.isLeft = isLeft;
				return returnValue;
			}
			else if (comparisonResult < 0) {
				isLeft = true;
				root = root.getLeftSubtree();
			}
			else if (comparisonResult > 0) {
				isLeft = false;
				root = root.getRightSubtree();
			}
			parent = n;
		}
		
		return returnValue;
	}
	
	public boolean insert(T val){ 
		IBinaryTreeNode<T> root = getRoot();
		if (root == null){
			setRoot(new BinaryTreeNode<T>(val));
			return true;
		}
		while(true){
			IBinaryTreeNode<T> r = root;
			int comparisonResult = comparator.compare(root.getData(), val);
			if (comparisonResult == 0) return false;
			else if (comparisonResult < 0){
				root = r.getLeftSubtree();
				if (root == null){
					r.setLeftSubtree(new BinaryTreeNode<T>(val));
					return true;
				}
			}
			else if (comparisonResult > 0){
				root = r.getRightSubtree();
				if (root == null){
					r.setRightSubtree(new BinaryTreeNode<T>(val));
					return true;
				}
			}
		}
	}
	
	public void delete(T val){
		SearchResult<T> searchResult = searchInner(val);
		IBinaryTreeNode<T> parent = searchResult.parent;
		IBinaryTreeNode<T> node = searchResult.node;
		if (node == null) return;
		
		if (parent == null && node.getChildren().size() == 0){ // is this only root 
			setRoot(null);
			return;
		}
		
		if (node.getChildren().size() == 0){
			if (parent != null){
				setSubtree(parent, null, searchResult.isLeft);
			}
			return;
		}
		
		if (node.getChildren().size() == 1){
			if (parent != null){
				setSubtree(parent, (IBinaryTreeNode<T>)node.getChildren().get(0), searchResult.isLeft);
			}
			return;
		}
		// we have two children then
		
		if (!isNonDeterministicRemoval){
			if (isDeterministicallyRemoveWithLeft){
				removeUsingLeftSubtree(node);
			}
			else{
				removeUsingRightSubtree(node);
			}
		}
		else{
			if (Math.random() > 0.5){
				removeUsingLeftSubtree(node);
			}
			else{
				removeUsingRightSubtree(node);
			}
		}
	}

	private void removeUsingLeftSubtree(IBinaryTreeNode<T> node) {
		SearchResult<T> inOrderResult = getInOrderPredecessor(node);
		IBinaryTreeNode<T> swapNode = inOrderResult.node;
		node.setData(swapNode.getData());
		if (inOrderResult.parent == node){
			node.setLeftSubtree(swapNode.getLeftSubtree());
		}
		else{
			inOrderResult.parent.setRightSubtree(swapNode.getLeftSubtree());
		}
	}
	
	private void removeUsingRightSubtree(IBinaryTreeNode<T> node) {
		SearchResult<T> inOrderResult = getInOrderSuccessor(node);
		IBinaryTreeNode<T> swapNode = inOrderResult.node;
		node.setData(swapNode.getData());
		if (inOrderResult.parent == node){
			node.setRightSubtree(swapNode.getRightSubtree());
		}
		else{
			inOrderResult.parent.setLeftSubtree(swapNode.getRightSubtree());
		}
	}
	
	private SearchResult<T> getInOrderPredecessor(IBinaryTreeNode<T> node){
		SearchResult<T> result = new SearchResult<T>();
		result.parent = null;
		result.node = node; 
		result.isLeft = false;
		IBinaryTreeNode<T> n = node.getLeftSubtree();
		do{
			result.parent = result.node;
			result.node = n;
			n = n.getRightSubtree();
		}while(n != null);
		return result;
		
	}
	
	private SearchResult<T> getInOrderSuccessor(IBinaryTreeNode<T> node){
		SearchResult<T> result = new SearchResult<T>();
		result.parent = null;
		result.node = node; 
		result.isLeft = false;
		IBinaryTreeNode<T> n = node.getRightSubtree();
		do{
			result.parent = result.node;
			result.node = n;
			n = n.getLeftSubtree();
		}while(n != null);
		return result;
		
	}
	
	private void setSubtree(IBinaryTreeNode<T> parent, IBinaryTreeNode<T> node,
			boolean isLeft) {
		if (isLeft){
			parent.setLeftSubtree(node);
		}
		else{
			parent.setRightSubtree(node);
		}
	}

	private static class SearchResult<T>{
		public IBinaryTreeNode<T> parent;
		public IBinaryTreeNode<T> node;
		public boolean isLeft;
		@Override
		
		public String toString() {
			return "SearchResult [parent=" + parent + ", node=" + node
					+ ", isLeft=" + isLeft + "]";
		}
	}
}